import numpy as np
import time
from multiprocessing import Pool, cpu_count
from multiprocessing.pool import TimeoutError

matrix = np.loadtxt('numbers.txt')

def find_all_scoring_rectangles(matrix):
    rectangles = []
    for y in range(len(matrix)):
        for x in range(len(matrix[0])):
            max_sum = 0  
            for height in range(1, len(matrix) - y + 1):
                for width in range(1, len(matrix[0]) - x + 1):
                    submatrix = [row[x:x + width]
                                 for row in matrix[y:y + height]]
                    sub_sum = sum(map(sum, submatrix))
                    if sub_sum > 10: 
                        break
                    if sub_sum == 10:
                        raw_rectangle = (
                            (x + 1, y + 1), (x + width, y + height))
                        rectangles.append(raw_rectangle)
                max_sum += matrix[y + height - 1][x]
                if max_sum > 10:  
                    break

    rectangles.sort(key=lambda rect: (
        1 if matrix[rect[0][1]-1][rect[0][0]-1] + matrix[rect[1][1]-1][rect[1][0]-1] == 10 else 0), reverse=True)

    return rectangles

def apply_scoring(matrix, rectangle):
    x1, y1 = rectangle[0]
    x2, y2 = rectangle[1]
    score_gained = 0
    for i in range(y1 - 1, y2):
        for j in range(x1 - 1, x2):
            if matrix[i][j] != 0:
                score_gained += 1
            matrix[i][j] = 0
    return score_gained

def worker(rectangle):
    updated_matrix = np.array(matrix, copy=True)
    score = apply_scoring(updated_matrix, rectangle)
    attempts = 1
    rectangles = [rectangle] 
    while True:
        next_rectangles = find_all_scoring_rectangles(updated_matrix)
        if not next_rectangles:
            break
        next_rectangle = next_rectangles[0]
        rectangles.append(next_rectangle)  
        score += apply_scoring(updated_matrix, next_rectangle)
        attempts += 1
    return rectangle, score, attempts, rectangles  

def find_best_solution(matrix, timeout):
    best_score = 0
    best_solution = []
    initial_rectangles = find_all_scoring_rectangles(matrix)

    print(f"初始矩形总数（第一步）：{len(initial_rectangles)}")

    total_attempts = 0
    start_time_global = time.time()
    with Pool(processes=cpu_count()) as pool:
        results = []
        for rectangle in initial_rectangles:
            try:
                result = pool.apply_async(worker, (rectangle,))
                results.append(result)
            except Exception as e:
                print(f"处理初始矩形 {rectangle} 出错：{e}")
                continue

        pool.close()
        start_time = time.time()
        elapsed_time = 0
        while elapsed_time < timeout:
            if all(result.ready() for result in results):
                break
            elapsed_time = time.time() - start_time

        if elapsed_time >= timeout:
            pool.terminate()

    for index, result in enumerate(results, 1):
        if result.ready():
            rectangle, score, attempts, rectangles = result.get() 
            total_attempts += attempts
            #print(f"从初始矩形 {index} {rectangle} 开始，经过 {attempts} 次尝试，获得最高得分: {score}")
            if score > best_score:
                best_score = score
                best_solution = rectangles
                best_initial_rectangle = rectangle
        # else:
            #print(f"从初始矩形 {index} 开始的处理超时")

    end_time_global = time.time()
    print(f"\n最佳得分：{best_score}")
    print(f"最佳初始矩形：{best_initial_rectangle}")
    # print(f"最佳解决方案：{best_solution}")
    print(f"总耗时：{end_time_global - start_time_global:.2f} 秒")
    print(f"所有初始矩形的尝试次数：{total_attempts}")
    print(
        f"每次尝试的平均耗时：{(end_time_global - start_time_global) / total_attempts:.4f} 秒")
    with open("coordinates.txt", "w") as file:
        for coordinate in best_solution:
            file.write(f"Rectangle:{coordinate}\n")

    return best_solution, best_score

if __name__ == '__main__':
    timeout = 25
    best_solution, best_score = find_best_solution(matrix, timeout)

    for rectangle in best_solution:
        apply_scoring(matrix, rectangle)

    print(matrix)
